package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Queue;
import com.tyrone.algorithm.priority.IndexMinPriorityQueue;

/**
 * Dijkstra 求最短路径树
 */
public class DijkstraSP {
    private DirectedEdge[] edgeTo;                  //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private double[] distTo;                        //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private IndexMinPriorityQueue<Double> pq;               //存放树中顶点与非树中顶点之间的有效横切边

    public DijkstraSP(EdgeWeightedDigraph G,int s){
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        pq=new IndexMinPriorityQueue<>(G.V());
        distTo[s]=0.0;
        pq.insert(s,0.0);
        while (!pq.isEmpty()){
            relax(G,pq.delMin());
        }
    }

    /**
     * 松弛图G中的顶点v
     * @param G
     * @param v
     */
    private void relax(EdgeWeightedDigraph G, int v){
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo(w)>distTo(v)+e.weight()){
                distTo[w]=distTo[v]+e.weight();
                edgeTo[w]=e;
                if (pq.contains(w)){
                    pq.changeItem(w,distTo(w));
                }else {
                    pq.insert(w,distTo(w));
                }
            }
        }
    }

    /**
     * 获取从顶点s到顶点v的最短路径的总权重
     * @param v
     * @return
     */
    public double distTo(int v){
        return distTo[v];
    }

    /**
     * 判断从顶点s到顶点v是否可达
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    /**
     * 查询从起点s到顶点v的最短路径中所有的边
     * @param v
     * @return
     */
    public Queue<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Queue<DirectedEdge> edges = new Queue<>();
        DirectedEdge e=null;
        while (true){
            e=edgeTo[v];
            if (e==null){
                break;
            }
            edges.enqueue(e);
            v=e.from();
        }
        return edges;
    }

}
